class WordDictionary(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.trie = {}

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        d = self.trie
        for ch in word:
            if ch not in d:
                d.update({ch:{}})
            d = d[ch]
        d.update({"end":None})

    def search(self, word):
        """
        Returns if the word is in the data structure. A word could
        contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """
        def find(seq, d):
            if d==None: return False
            if len(seq)==0:
                if "end" in d: return True
                else: return False

            ret = False

            ch = seq[0]
            if ch in d:
                ret = find(seq[1:], d[ch])
            elif ch=='.':
                for val in d.values():
                    ret = ret or find(seq[1:], val)
            return ret
        
        return find(word, self.trie)

# Your WordDictionary object will be instantiated and called as such:
wordDictionary = WordDictionary()
wordDictionary.addWord("at")
wordDictionary.addWord("and")
wordDictionary.addWord("an")
wordDictionary.addWord("add")
print(wordDictionary.search("a"))
print(wordDictionary.search(".at"))
wordDictionary.addWord("bat")
print(wordDictionary.search(".at"))
print(wordDictionary.search("an."))
print(wordDictionary.search("a.d."))
print(wordDictionary.search("b."))
print(wordDictionary.search("a.d"))
print(wordDictionary.search("."))